"""
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1:
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
"""
# 题目大意 
"""给你一个链表，删除链表的倒数第 n 个节点，并且返回链表的头节点。"""
"""常规思路是遍历一遍链表，求出链表长度，再遍历一遍到对应位置，删除该位置上的节点。
如果用一次遍历实现的话，可以使用快慢指针。让快指针先走 n 步，然后快慢指针、慢指针再同时走，每次一步，这样等快指针遍历到链表尾部的时候，慢指针就刚好遍历到了倒数第 n 个节点位置。将该位置上的节点删除即可。
需要注意的是要删除的节点可能包含了头节点。我们可以考虑在遍历之前，新建一个头节点，让其指向原来的头节点。这样，最终如果删除的是头节点，则删除原头节点即可。返回结果的时候，可以直接返回新建头节点的下一位节点。"""


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        newhead = ListNode(0,head)
        fast = head
        slow = newhead
        while n:
            fast = fast.next
            n -= 1
        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return newhead.next
        # 方法一：计算链表长度
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def getLength(head:ListNode) -> int:
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        dummy = ListNode(0, head)
        length = getLength(head)
        curr = head
        for i in range(1, length - n + 1):
            curr = cuur.next
        curr.next = curr.next.next
        return dummy.next

        # 方法二：使用栈的方式
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        stack = list()
        curr = dummy
        while curr:
            stack.append(curr)
            curr = curr.next
        for i in range(n):
            stack.pop()
        prev = stack[-1]
        prev.next = prev.next.next
        return dummy.next
